package leetcode_acm.leetcode_1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月10日 11:23
 */
public class PathSum {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }
    private List<List<Integer>> list;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        list = new LinkedList<>();
        traverse(root,new LinkedList<>(),targetSum-root.val);
        return list;
    }

    private void traverse(TreeNode root,LinkedList<Integer> path,int targetSum){
        if(root.left == null && root.right == null && targetSum == 0){
            list.add(new LinkedList<>(path));
        }
        if(root.left != null){
            path.addLast(root.left.val);
            traverse(root.left,path,targetSum-root.left.val);
            path.removeLast();
        }
        if(root.right != null){
            path.addLast(root.right.val);
            traverse(root.right,path,targetSum-root.right.val);
            path.removeLast();
        }
    }
}
